package labuladong.动态规划;

import java.util.Arrays;

public class 子集背包问题 {

    public static boolean canPartition(int[] nums) {
        int allSum = Arrays.stream(nums).sum();
        if (allSum%2 != 0) return false;
        int sum = allSum / 2;
        int len = nums.length;
        int[][] dp = new int[len+1][sum+1];
        for (int i=0; i<=len; i++) dp[i][0] = 1;

        for (int i=1; i<=len; i++) {
            for (int j=1; j<=sum; j++) {
                if (j - nums[i-1] < 0) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[len][sum] == 1 ? true : false;
    }

    public static void main(String[] args) {
        System.out.println(canPartition(new int[]{1, 5, 11, 5}));
    }
}
